package com.zjsru.plan2024.oneday;

import java.util.Arrays;

/**
 * 3233. 统计不是特殊数字的数字数量
 *
 * @Author: cookLee
 * @Date: 2024-11-22
 */
public class NonSpecialCount {

    /**
     * 主
     * \
     * 输入： l = 5, r = 7
     * <p>
     * 输出： 3
     * <p>
     * 解释：
     * <p>
     * 区间 [5, 7] 内不存在特殊数字。
     * \
     * 输入： l = 4, r = 16
     * <p>
     * 输出： 11
     * <p>
     * 解释：
     * <p>
     * 区间 [4, 16] 内的特殊数字为 4 和 9。
     *
     * @param args args
     */
    public static void main(String[] args) {
        NonSpecialCount nonSpecialCount = new NonSpecialCount();
        int l = 5;
        int r = 7;
        System.out.println(nonSpecialCount.nonSpecialCount(l, r));
    }

    public int nonSpecialCount(int l, int r) {
        //假设全部满足要求
        int ans = r - l + 1;
        int sqr = (int) Math.sqrt(r);
        int[] count = new int[sqr + 1];
        Arrays.fill(count, 0);

        for (int i = 2; i <= sqr; i++) {
            if (count[i] == 0) {
                //特殊数字，因为平方数除去自身和 1 之后的另一个因子一定是一个质数
                if (i * i >= l && i * i <= r) {
                    ans -= 1;
                }
                //以 i 为步长，将所有 i 的倍数标记为已处理
                for (int j = i * 2; j <= sqr; j += i) {
                    count[j] = 1;
                }
            }
        }
        return ans;
    }

}
